package leetcode;

import java.util.*;

/**
 * @author MaoLin Wang
 * @date 2020/10/10 2:34 下午
 */
public class _39组合总和 {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length==0){
            return new ArrayList<>();
        }
        List<List<Integer>>res=new ArrayList<>();

        Arrays.sort(candidates);
        Deque<Integer>path=new ArrayDeque<>();
        dfs(candidates,0,target,path,res);
        return res;
    }

    private static void dfs(int[] candidates, int begin, int target,Deque<Integer> path, List<List<Integer>> res) {

        if (target==0){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < candidates.length; i++) {
            if (target-candidates[i]<0){
                break;
            }
            path.addLast(candidates[i]);;
            dfs(candidates, i, target-candidates[i], path, res);
            path.removeLast();
        }
    }
}
